package chapter1.fundamentals.exercise;

import edu.princeton.cs.algs4.StdRandom;

/**
 * @author quanlinlin on 2018/11/3 10:48.
 * @version 1.0
 */
public class E_30 {

    public static void main(String[] args) {
        int n = StdRandom.uniform(10);
        boolean[][] arr = new boolean[n][n];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                arr[i][j] = isCoprime(i, j) ? true : false;
                System.out.print("i:" + i + ",j:" + j + "," + arr[i][j] + "\t");
            }
            System.out.println();
        }

    }

    public static int gcd(int a, int b) {
        if (a < b) {
            return gcd(b, a);
        }
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    /**
     * 1虽不是质数，但与任何正整数都是互质数。
     *
     * @param a
     * @param b
     * @return
     */
    public static boolean isCoprime(int a, int b) {
        return gcd(a, b) == 1;
    }


}
